package binarytree;

import java.util.*;

/**
 * @Author liangzai
 * @Description:
 */
public class BinaryTree {
    public int nodesize;
    public int leafNode;
    TreeNode root = new TreeNode('A');

    public TreeNode creatTree(){
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        TreeNode I = new TreeNode('I');

        root.left = B;
        root.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.left = H;
        H.right = I;
        return root;
    }

    public void preOrder(TreeNode root){
        if(root == null){
            return ;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //非递归前序遍历二叉树
    public void preOrderNor(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pcur = root;
        while(pcur!=null || !stack.isEmpty()){
            while(pcur!=null){
                stack.push(pcur);
                pcur = pcur.left;
                System.out.print(stack.peek().val+" ");
            }
            pcur = stack.pop().right;
        }
        System.out.println();
    }

    public void inOrder(TreeNode root){
        if(root == null){
            return ;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);

    }

    //非递归中序遍历二叉树
    public void inOrderNor(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pcur = root;
        while(pcur!=null || !stack.isEmpty()){
            while(pcur!=null){
                stack.push(pcur);
                pcur = pcur.left;
            }
            System.out.print(stack.peek().val+" ");
            pcur = stack.pop().right;
        }
        System.out.println();
    }

    public void outOrder(TreeNode root){
        if(root == null){
            return ;
        }
        outOrder(root.left);
        outOrder(root.right);
        System.out.print(root.val+" ");
    }

    //非递归后序遍历二叉树
    public void outOrderNor(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pcur = root;
        TreeNode prev = null;
        while(pcur!=null || !stack.isEmpty()){
            while(pcur!=null){
                stack.push(pcur);
                pcur = pcur.left;
            }
            TreeNode top = stack.peek();
            if(top.right==null || top.right == prev){
                System.out.print(stack.pop().val+" ");
                prev = top;
            }else{
                pcur = top.right;
            }
        }
        System.out.println();
    }

    public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        nodesize++;
        size(root.left);
        size(root.right);
        return nodesize;
    }

    public int size2 (TreeNode root){
        if(root == null){
            return 0;
        }
        return size2(root.left)+size2(root.right)+1;
    }

    public int getleafNode(TreeNode root){
        if(root == null){
            return 0;
        }

        if(root.right == null && root.left == null){
            return leafNode+=1;
        }
        getleafNode(root.left);
        getleafNode(root.right);
        return leafNode;
    }

    public int getLeafNode2(TreeNode root){
        if(root == null){
            return 0;
        }

        if(root.right == null && root.left == null){
            return 1;
        }
        return getLeafNode2(root.left) + getLeafNode2(root.right);
    }


    public int getKlevelNode(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKlevelNode(root.left,k-1)+getKlevelNode(root.right,k-1);
    }

    public int getMaxDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        return getMaxDepth(root.left)>getMaxDepth(root.right)?getMaxDepth(root.left)+1:getMaxDepth(root.right)+1;
    }

    public TreeNode find(TreeNode root,char val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode retL = find(root.left,val);
        if(retL != null){
            return retL;
        }
        TreeNode retR = find(root.right,val);
        if(retR != null){
            return retR;
        }
        return null;
    }

    public boolean isSameTree(TreeNode p ,TreeNode q){
        if(q!=null && p==null || q==null && p!=null){
            return false;
        }
        if(q==null && p==null){
            return true;
        }
        if(q.val == p.val){
            return true;
        }

        return isSameTree(p.left,q.left) && isSameTree(p.right,p.left);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null){
            return false;
        }
        if(isSameTree(root,subRoot) ){
            return true;
        }
        // if(isSubtree(root.left,subRoot)) {
        //     return true;
        // }
        // if(isSubtree(root.right,subRoot)) {
        //     return true;
        // }
        // return false;
        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;
        mirrorTree(root.right);
        mirrorTree(root.left);
        return root;
    }

    private boolean checkLeafNode(TreeNode left,TreeNode right){
        if(left !=null && right == null || left==null && right != null){
            return false;
        }

        if(left == null && right == null){
            return true;
        }

        if(left.val != right.val){
            return false;
        }
        return checkLeafNode(left.left,right.right) && checkLeafNode(left.right, right.left);
    }

    public boolean checkSymmetricTree(TreeNode root) {
        if(root == null){
            return true;
        }
        return checkLeafNode(root.left, root.right);
    }

    private int getMaxDepth2(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftlong = getMaxDepth2(root.left);
        int rightlong = getMaxDepth2(root.right);

        return leftlong>rightlong?leftlong+1:rightlong+1;
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int a = getMaxDepth2(root.left);
        int b = getMaxDepth2(root.right);

        // if((a>=0 ? a : -a) >= 2){
        //     return false;
        // }
        return Math.abs(a-b)<2 && isBalanced(root.left) && isBalanced(root.right);
    }

    //时间复杂度O(n),字节面试题
    public int getMaxDepth3(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftlong = getMaxDepth3(root.left);
        if(leftlong < 0){
            return -1;
        }
        int rightlong = getMaxDepth3(root.right);
        if(rightlong < -1){
            return -1;
        }
        if(leftlong == -1 || rightlong == -1 || Math.abs(leftlong-rightlong)>=2){
            return -1;
        }else{
            return Math.max(leftlong,rightlong)+1;
        }
    }
    public boolean isBalanced2(TreeNode root) {
        if(root == null) return true;
        return getMaxDepth3(root) >= 0;
    }

    //二叉搜索树 转换为 双向链表
    static TreeNode prev = null;
    private void ConvertChild(TreeNode root){
        if(root == null){
            return ;
        }
        ConvertChild(root.left);
        root.left = prev;
        if(prev!=null){
            prev.right = root;
        }
        prev = root;
        ConvertChild(root.right);
    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        ConvertChild(pRootOfTree);
        while(pRootOfTree.left != null){
            pRootOfTree = pRootOfTree.left;
        }
        return pRootOfTree;
    }

    //以前序遍历 创建一个二叉树
    private int i = 0;
    public TreeNode createTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        } else {
            i++;
        }
        return root;
    }

    public void inOder(TreeNode root) {
        if (root == null) {
            return ;
        }
        inOder(root.left);
        System.out.print(root.val + " ");
        inOder(root.right);
    }

    //层序遍历二叉树
    public void levelOrder(TreeNode root){
        if(root==null){
            return ;
        }
        Queue<TreeNode> list = new LinkedList<>();
        list.offer(root);
        while(!list.isEmpty()){
            TreeNode pcur = list.poll();
            System.out.print(pcur.val+" ");
            if(pcur.left!=null){
                list.offer(pcur.left);
            }
            if(pcur.right!=null){
                list.offer(pcur.right);
            }
        }
        System.out.println();
    }

    //层序遍历二叉树(每一行为一组)
    public List<List<Character>> levelOrder2(TreeNode root) {
        List<List<Character>> list = new LinkedList<>();
        if(root==null){
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Character> list1 = new ArrayList<>(size);
            while(size>0) {
                TreeNode pcur = queue.poll();
                list1.add(pcur.val);
                if (pcur.left != null) {
                    queue.offer(pcur.left);
                }
                if (pcur.right != null) {
                    queue.offer(pcur.right);
                }
                size--;
            }
            list.add(list1);
        }
        return list;
    }

    //判断是否是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if(root==null){
            return true;
        }
        int flag = 0;
        Queue<TreeNode> list = new LinkedList<>();
        list.offer(root);
        while(flag==0){
            TreeNode pcur = list.poll();
            if(pcur==null) {
                int size = list.size();
                for (int i = 0; i < size; i++) {
                    if(list.poll()!=null) {
                        return false;
                    }
                }
               break;
            }
            list.offer(pcur.left);
            list.offer(pcur.right);
        }
        return true;
    }

    //找到两个节点的最早公共父节点
    public TreeNode lowestCommonAncestor(TreeNode root,  TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root ==p || root == q) {
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if(leftTree != null && rightTree != null) {
            return root;
        }else if(leftTree != null) {
            return leftTree;
        }else {
            return rightTree;
        }
    }

    /**
     *
     * @param root
     * @param node 找的节点
     * @param stack 存储到栈当中
     */
    public boolean getPath(TreeNode root,
                           TreeNode node,
                           Stack<TreeNode> stack) {
        if(root == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean ret = getPath(root.left,node,stack);
        if(ret) {
            return true;
        }
        ret = getPath(root.right,node,stack);
        if(ret) {
            return true;
        }
        stack.pop();
        return false;
    }


    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        //1.获取路径上的所有节点
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);

        //2. 比较两个栈的大小，多的出size个
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        if(sizeP > sizeQ) {
            int size = sizeP - sizeQ;
            while (size != 0) {
                stackP.pop();
                size--;
            }
        }else {
            int size = sizeQ - sizeP;
            while (size != 0) {
                stackQ.pop();
                size--;
            }
        }
        //3. 每次出数据 看栈顶元素是否一样
        while (!stackP.isEmpty() && !stackQ.isEmpty()) {
            if (stackP.peek() == stackQ.peek()) {
                return stackP.peek();
            } else {
                stackQ.pop();
                stackP.pop();
            }
        }

        return null;
    }

    //根据二叉树创建字符串
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }

    private StringBuilder tree2strChild(TreeNode root ,StringBuilder stringBuilder){
        if(root==null){
            return null;
        }
        stringBuilder.append(root.val);
        if(root.left!=null){
            stringBuilder.append('(');
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(')');
        }else{
            if(root.right!=null){
                stringBuilder.append("()");
            }else{
                return null;
            }
        }
        if(root.right!=null){
            stringBuilder.append('(');
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(')');
        }else{
            return null;
        }
        return stringBuilder;
    }


}
